package com.zjj.lbw.algorithm.recursion;

/**
 * @author zhanglei.zjj
 * @description leetcode_70 爬楼梯
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 * 示例 1：
 *
 * 输入：n = 2
 * 输出：2
 * 解释：有两种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶
 * 2. 2 阶
 * 示例 2：
 *
 * 输入：n = 3
 * 输出：3
 * 解释：有三种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶 + 1 阶
 * 2. 1 阶 + 2 阶
 * 3. 2 阶 + 1 阶
 *
 * 提示：
 *
 * 1 <= n <= 45
 *
 * @date 2023/3/12 12:02
 */
public class ClimbStairs_leetcode_70 {
    // public int climbStairs(int n) {
    //     if (n == 1) {
    //         return 1;
    //     }
    //     if (n == 2) {
    //         return 2;
    //     }
    //     return climbStairs(n - 1) + climbStairs(n - 2);
    // }

    // 带HashMap的递归
    // public int climbStairs(int n) {
    //     if (n==1) {
    //         return 1;
    //     }
    //     if (n==2) {
    //         return 2;
    //     }

    //     if (map.containsKey(n)) {
    //         return map.get(n);
    //     } else {
    //         int result = climbStairs(n - 1) + climbStairs(n - 2);
    //         map.put(n, result);
    //         return result;
    //     }
    // }

    // 循环解法
    int pre = 2;
    int prePre = 1;
    int result = 0;
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if(n == 2) {
            return 2;
        }
        for(int i = 3; i <= n; i++) {
            result = pre + prePre;
            prePre = pre;
            pre = result;
        }
        return result;
    }
}
